DAY 3 試題

問題描述

最長不重複子字串長度
給定一個字串 s，找出其中不包含重複字元的 最長子字串 的長度。

例子：
Input: s = "abcabcbb"
Output: 3
Explanation: 最長不重複子字串是 "abc"，長度為 3。

Input: s = "bbbbb"
Output: 1
Explanation: 最長不重複子字串是 "b"，長度為 1。

Input: s = "pwwkew"
Output: 3
Explanation: 最長不重複子字串是 "wke"，長度為 3。

解題思路

這是一道經典的滑動視窗（Sliding Window）問題。我們需要找到字串中不含重複字元的最長子字串。通常，兩種策略可以有效解決這個問題：

1. 使用哈希表 來追蹤每個字元的最新出現位置，並配合滑動視窗調整不重複子字串的範圍。
2. 使用固定大小的陣列，來代替哈希表追蹤字元，這樣可以有效避免使用哈希表的額外開銷。

我們將分別展示這兩種方法，並比較它們的性能和複雜度。

滑動視窗（Sliding Window）

滑動視窗（Sliding Window）是一種高效的算法技術，主要用於解決需要在序列（如字串、陣列）中進行部分處理的問題。這種方法通過維持一個「視窗」在序列上，並在需要的時候滑動（即移動視窗的起始和結束位置），可以大大提高算法的效率。

基本概念

視窗（Window）：

• 這是一個在序列上滑動的區域，可以是固定大小的，也可以是動態大小的。
• 視窗的大小可以根據問題的需求來確定。

滑動（Sliding）：

• 當視窗向右移動時，通常會更新視窗內的元素（例如，增加新元素或刪除舊元素）。
• 視窗的移動可以是逐步的，每次移動一步，或者按一定的規則移動。

使用哈希表的解法

使用滑動視窗配合哈希表來追蹤字元的最新出現位置。每次遇到重複字元時，我們將滑動視窗的左邊界更新到重複字元的下一個位置，以保證子字串中不會有重複的字元。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> char_index;  // 哈希表：記錄每個字元最後一次出現的位置
        int max_len = 0;  // 記錄當前找到的最長子字串長度
        int start = 0;    // 滑動視窗的左邊界

        // 逐字元遍歷整個字串
        for (int i = 0; i < s.length(); i++) {
            char current_char = s[i];  // 目前處理的字元

            // 如果當前字元在哈希表中且位置大於或等於 start，則更新 start
            if (char_index.find(current_char) != char_index.end() && char_index[current_char] >= start) {
                start = char_index[current_char] + 1;  // 移動視窗的左邊界到重複字元的下一個位置
            }

            // 更新哈希表中當前字元的位置
            char_index[current_char] = i;

            // 計算當前不重複子字串的長度，並更新最大長度
            max_len = max(max_len, i - start + 1);
        }

        return max_len;
    }
};

解法分析：

• 哈希表：使用哈希表來記錄每個字元的最新出現位置。
• 滑動視窗：當遇到重複字元時，將視窗的左邊界 start 移動到重複字元的下一個位置，保證當前子字串不含重複字元。
• 時間複雜度：O(n)，其中 n 是字串的長度，因為每個字元最多只會被訪問兩次（一次加入視窗，一次移出）。
• 空間複雜度：O(min(n, m))，其中 n 是字串長度，m 是字符集大小（例如 128 個 ASCII 字符）。

使用大小固定的陣列

在這個解法中，我們使用一個大小固定的陣列來取代哈希表。由於字符集是有限的（ASCII 字符），可以使用長度為 128 的陣列來追蹤每個字元的最新位置，這樣可以減少額外的空間開銷。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> char_index(128, -1);  // 大小為 128 的陣列，初始化為 -1 表示未出現過的字元
        int max_len = 0;  // 記錄當前找到的最長子字串長度
        int start = 0;    // 滑動視窗的左邊界

        // 逐字元遍歷整個字串
        for (int i = 0; i < s.length(); i++) {
            char current_char = s[i];  // 目前處理的字元

            // 如果該字元上次出現的位置大於或等於 start，更新 start
            if (char_index[current_char] >= start) {
                start = char_index[current_char] + 1;  // 更新 start 到重複字元的下一個位置
            }

            // 更新字元的最後出現位置
            char_index[current_char] = i;

            // 計算當前不重複子字串的長度，並更新最大長度
            max_len = max(max_len, i - start + 1);
        }

        return max_len;
    }
};

解法分析：

• 陣列：我們使用大小為 128 的陣列，根據字元的 ASCII 值直接更新它們的最後出現位置。
• 滑動視窗：與使用哈希表的方式相同，當遇到重複字元時，將視窗的左邊界 start 移動到重複字元的下一個位置。
• 時間複雜度：同樣為 O(n)，因為每個字元最多只會被訪問兩次。
• 空間複雜度：O(1)，因為我們只使用了一個固定大小的陣列，與字串的長度無關。

比較與總結

什麼時候使用哪一個方法？

哈希表解法：適合處理字符集不固定且數量龐大的情況，比如使用 Unicode 字符的場合。
陣列解法：當你知道字符集是固定且較小時（如 ASCII 字符集），使用陣列會更加高效，並且能節省空間。

由於本題只有128個不同字符，因此在這裡使用陣列解法會比使用哈希表解法來的快速。

以上是第三天的自學內容分享，謝謝大家。